package java学习.代码随想录.动态规划;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/8 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 最长重复子数组 {
    /**
     * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
     *
     * 示例：
     * 输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。
     *
     * dp[i][j]: n1[i]结尾 和 n2[j]结尾 的，公共连续子串最长 长度。
     * todo 公共子数组相当于 子串是连续的
     * 公式：若 两元素相等，则 公共长度+1 ，在之前的基础上+1
     *      dp[i][j] = dp[i-1][j-1]+1
     * 否则不是连续的，置零 (不构成公共子数组)
     *
     * 初始化 默认都是0
     */
    public static int findLength1(int[] nums1, int[] nums2) {
        int count = 0;
        int [][]dp = new int[nums1.length+ 1][nums2.length+ 1];
        for(int i = 1; i<nums1.length+1 ;i++){
            for (int j = 1; j < nums2.length +1 ; j++) {
                if (nums1[i-1]==nums2[j-1]){
                    dp[i ][j ] =dp[i-1][j-1]+1;
                }
                count  =Math.max(count,dp[i ][j ]);
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print (dp[i][j]+" ");
            }
            System.out.println();
        }

        return count;
    }
    public static int findLength(int[] nums1, int[] nums2) {
        int count = 0;
        int [][]dp = new int[nums1.length+ 1][nums2.length+ 1];
        for(int i = 0; i<nums1.length ;i++){
            for (int j = 0; j < nums2.length ; j++) {
                if (nums1[i]==nums2[j]){
                    dp[i+1][j+1] =dp[i ][j ]+1;
                }
                count  =Math.max(count,dp[i+1][j+1]);
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print (dp[i][j]+" ");
            }
            System.out.println();
        }
//        System.out.println(Arrays.deepToString(dp));

        return count;
    }




    public static void main(String[] args) {
        int[] nums1 = {1,2,3,2,1};
        int[] nums2 = {3,2,1,4,7};
        System.out.println(findLength(nums1,nums2));
        System.out.println(findLength1(nums1,nums2));

    }
}
